# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        matrix = [True] * (rows*cols)
        # print(matrix)
        self.nums = 0
        self.find_ways(threshold, rows, cols, matrix, 0, 0)
        return self.nums
    def find_ways(self, threshold, rows, cols, matrix, i, j):
        if i >= rows or j >= cols  or i < 0 or j < 0 or not matrix[i*cols+j]:
            return False
        row_digit = []
        i_copy = i
        while i_copy:
            row_digit.append(i_copy%10)
            i_copy = i_copy//10
        col_digit = []
        j_copy = j
        while j_copy:
            col_digit.append(j_copy%10)
            j_copy = j_copy//10
        if sum(row_digit) + sum(col_digit) > threshold:
            return False
        self.nums += 1
        matrix[i*cols+j] = False
        self.find_ways(threshold, rows, cols, matrix, i-1, j)
        self.find_ways(threshold, rows, cols, matrix, i+1, j)
        self.find_ways(threshold, rows, cols, matrix, i, j-1)
        self.find_ways(threshold, rows, cols, matrix, i, j+1)
test = Solution()
print(test.movingCount(10,1,100))